package 力扣.贪心;

/**
 * 贪心算法：当前最好的，当前可行的，要寻找一个贪心策略
 */
public class 种花问题605 {
    public static void main(String[] args) {
//        测试用例
//        int[] arr2=new int[]{0,0,1,0,1};//101  010
//        int[] arr2=new int[]{0,0,1,0,0,1};//101  010
//        int[] arr2=new int[]{1,0,0,0,0,1};//101  010
//        int[] arr2=new int[]{0,0,1,0,1};//101  010
//        int[] arr2=new int[]{1,0,0,0,1,0,0};//101  010
//        int[] arr2=new int[]{0};//101  010
        int[] arr2=new int[]{1};//101  010
        boolean b = canPlaceFlowers(arr2, 1);
        System.out.println(b);
    }
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        int end=flowerbed.length-1;
        //边界条件：两个及以下的元素
        if (n==0){
            return true;
        }
        if (end<2){
            if (end==0&&flowerbed[0]==0){
                n--;
            } else if (end==1){
                if (flowerbed[0]==0&&flowerbed[1]==0){
                    n--;
                }
            }else
                return false;
            if (n <= 0) {
                return true;
            }else
                return false;
        }
        //贪心策略，当前元素和（+1位元素、-1位元素）都为0，才能赋值为1
        for (int i = 0; i <flowerbed.length-1 ; i++) {
            if (flowerbed[i]==0&&flowerbed[i+1]==0){//001
                if (i>0){
                    if (flowerbed[i-1]!=1){
                        flowerbed[i]=1;
                        n--;
                    }
                }else{
                    //边界条件:当i=0时，即第一个元素，就不用判断它的前一个元素了
                    flowerbed[i]=1;
                    n--;
                }
            }

        }
//        边界条件：当倒数两个元素为0、0时，就可以直接给最后一个元素插上花
        if (flowerbed[end-1]==0&&flowerbed[end]==0){
            flowerbed[end]=1;
            n--;
        }
        if (n <= 0){
            return true;
        }else
            return false;
    }
}
